class Solution {
    public static int[][] merge(int[][] intervals) {
        int n = intervals.length;
        intervals = qSort(intervals, 0, n-1);

        int[][] res = new int[n][2];
        res[0] = intervals[0];
        int j = 0;
        for (int i = 1; i < n; i++) {
            int[] pre = res[j];
            int[] cur = intervals[i];
            if (pre[1] < cur[0]) {
                res[++j] = cur;
            } else {
                res[j][1] = Math.max(pre[1], cur[1]);;
            }
        }

        int[][] result = new int[j+1][2];
        for (int i = 0; i <= j; i++) {
            result[i] = res[i];
        }
        return result;
    }

    public static int[][] qSort(int[][] array, int start, int end) {
        if (start < end) {
            int pointer = partition(array, start, end);
            qSort(array, start, pointer-1);
            qSort(array, pointer+1, end);
        }
        return array;
    }

    private static int partition(int[][] array, int start, int end) {
        int pivot = array[end][0];
        int pointer = start;
        for (int i = start; i < end; i++) {
            if (array[i][0] < pivot) {
                int[] tmp = array[i];
                array[i] = array[pointer];
                array[pointer] = tmp;
                pointer++;
            }
        }

        int[] tmp = array[end];
        array[end] = array[pointer];
        array[pointer] = tmp;
        return pointer;
    }
}